1. Field of the Invention
The present invention relates generally to methods and apparatus for detecting and correcting read errors in a disc drive and, more particularly but not by way of limitation, to improvements in error detection and correction methods and apparatus employing Reed-Solomon codes.
2. Brief Description of the Prior Art
Disc drives are commonly used to store computer files and, to this end, a disc drive is comprised of one or more rotating discs having magnetizable surface coatings for storage of the files along data tracks magnetically defined in the coatings. Consequently, a file can be stored by magnetizing a data track in a pattern that reflects the contents of the file. To retrieve a previously stored file, the magnetic field produced by the magnetized data track is sensed by a read head to produce a time varying signal that is used to generate a received word that, in the absence of errors, will be a data word, including data elements of which the file is comprised, that was stored to the data track.
While disc drives have proven to be reliable devices for storing large quantities of user information, read errors do, at times, occur in the reading of a data track with the result that the received word differs from the code word that was stored along the data track. Such read errors, if uncorrected, will cause the collection of data elements that are returned to the host computer to differ from the file that was stored so that the information that is returned to a host computer will not be the file that was stored. In order to retrieve files that were stored, it has become common practice to provide disc drives with error correction circuitry to correct read errors in the received word recovered from a data track.
In many cases, the error correction circuitry is based on Reed-Solomon encoding in which data elements of a file to be stored are treated as the coefficients of a polynomial defined in a Galois field. The polynomial is completed with a plurality of additional data elements, or code elements, to form a data word that is an integral multiple of a code generating polynomial having known roots in the Galois field. Subsequently, when the data track is read, the received word is treated as a polynomial which, in the absence of read errors, will have the same coefficients as the data word that was written to the data track when the file was stored. In the Reed-Solomon scheme, the received polynomial is evaluated at each of the roots of the code generating polynomial to generate a syndrome having a number of components equal to the number of roots of the code generating polynomial and the syndrome components can then be used to detect and/or correct any errors that may have occurred in the reading of the file.
A known approach for error correction based upon Reed-Solomon encoding is to employ "on the fly" error correction circuitry to correct up to a selected number of errors with an example being the circuitry disclosed in U.S. Pat. No. 4,494,234, issued Jan. 15, 1985 to Patel. In the circuitry described by Patel, a syndrome having six components is generated to permit correction of up to three read errors in a received word. The Patel circuit relies upon inconsistencies in error locations; that is, the data elements that are identified to be erroneous, to detect the presence of a larger number of errors in the reading of the received word from the data track. However, it is possible for more than three read errors to occur without the generation of inconsistencies in the identified error locations. In such cases, the circuit may correct data elements at error locations which may bear no relation to the locations at which read errors have actually occurred to introduce additional errors into the sequence and result in the return of incorrect data to the computer in place of the file that was stored.
While, in principle, this problem can be overcome by the use of an error correction approach that permits the correction of a large number of errors, hardware required to carry out such an approach would be very complex or, if the error correction were carried out in software, the time required to implement the scheme would be undesirably long. Such complexity, or time requirements, generally make such an approach impractical for correction of more than about three errors.
A second approach known in the art is to provide a disc drive with circuitry, or software, that corrects one read error and unambiguously detects the presence of more than one read error. While such an approach overcomes the problem encountered with the pure error correction approach, it introduces another problem.
If two errors occur, an event that occurs infrequently but one that is becoming increasingly more common as data track transfer rates increase, a sector of a data track at which a file is stored must be reread. Rereading a data track requires that the disc on which the sector is located be rotated through nearly a complete revolution before rereading of the sector can be commenced. Consequently, reading of a file will be interrupted for the time required for the sector to return to the read head. Such time, approximately 10 milliseconds, is an unacceptably long time by computer standards.
An approach for solving this problem, by correcting up to two errors and detecting the occurrence of more than two errors, has been suggested by R. H. Deng and D. J. Costello. Jr. in an article entitled "Decoding of DBEC-TBED Reed-Solomon Codes" found at IEEE Trans. Comput., Vol. 36-C, pp 1359-1363 (1987). While the Deng and Costello suggestion could provide a basis for a workable error detection and correction system, such a system would be unable to completely distinguish between the occurrence of two and three errors without a redetermination of the syndrome after correction of a received word assuming the occurrence of two errors. This necessity for redetermination of the syndrome to determine whether a sector of data should be reread or corrected made the Deng and Costello suggestion impractical.